Finding minimal cost paths is important in many practical logistical applications including transportation, communication routing, and robot planning. The problem is to find a path from a source to a destination under some constraint, for example, a best path to the airport such that one neither arrives too early nor misses a deadline.
The invention is concerned with problems that can be modeled as a stochastic graph. A stochastic graph includes nodes connected by arcs. The arcs represent the paths that can form a potential minimal expected cost path, and the nodes are intermediate points where alternative subpaths can be selected. In a stochastic graph, a cost of traversing an arc is neither fixed nor predictable. Instead the cost is a random variable drawn from a probability distribution function associated with the arc. Typically, the random variable represents a ‘length’ of the arc, the time to traverse the arc, a financial cost, or a physical quantity. Almost all real-world planning and logistic problems have stochastic costs.
There are adaptive and non-adaptive approaches to optimal traversals of the graph. An adaptive method gives a policy in which one receives new information upon arriving at each node and that information is used to select the next arc. This new information makes the problem much easier. For this reason, most of the prior art revolves around adaptive methods. When new information is not forthcoming at every node, one must use non-adaptive methods to select chains of arcs that form paths. In the stochastic, setting this is generally a much harder problem.
Traditionally, the work on path planning in stochastic graphs has focused on a notion of shortest paths according to some expectation, Papadimitriou, C. H. and Yannakakis, M., “Shortest paths without a map,” Theoretical Determiner Science 84: pp. 127-150, and Bertsekas, D. P. and Tsitsiklis, J. N., “An analysis of stochastic shortest path problems,” Math. Oper. Res. 16 (3): pp. 580-595, 1991.
Some models associate a cumulative cost with each node. The cumulative cost depends on the time it takes to traverse the arcs to reach the node. By storing many such costs from many paths to each node, one can approximate the uncertainty in the problem, Chabini, I., “Algorithms for k-Shortest Paths and Other Routing Problems in Time-Dependent Networks,” Transportation Research Part B: Methodological, 2002, and Miller-Hooks, E. D., and Mahmassani, H. S., “Least Expected Time Paths in Stochastic, Time-Varying Transportation Networks,” Transportation Science, 34, pp. 198-215, 2000. Such approaches generally suffer exponential running time, unbounded approximation error, or both.
However, there has been little work on decision theoretic models, which directly incorporate uncertainty, and find the minimal expected cost path on the basis of a comprehensive measure of user utility and all available distributional information of the stochastic arc lengths. In that setting, the utility or cost of a path can be an arbitrary function of its total length, and both are random variables. To make optimal decisions, one must integrate out the randomness and evaluate paths according to their expected cost, which may be quite unrelated to their expected lengths.
Most prior art methods minimize an expected length of paths from the source to the destination, or a combination of expected lengths and expected costs such as bicriterion problems, J. Mote, I. Murthy, and D. Olson, “A parametric approach to solving bicriterion shortest path problems,” European Journal of Operational Research, 53:81-92, 1991, and S. Pallottino and M. G. Scutella, “Shortest path processes in transportation models: Classical and innovative aspects,” Technical Report TR-97-06, Universita di Pisa Dipartimento di Informatica, 1997.
Some methods use a decision theoretic model, R. P. Loui, “Optimal paths in graphs with stochastic or multi-dimensional weights,” Communications of the ACM, 26:670-676, 1983. However, Loui only considers monotone increasing costs. These are arguably easier because that model admits exact efficient solutions for special cases, such as linear and exponential objective functions.
An adaptive method for finding minimal cost paths that maximizes the probability of arriving before the deadline is described by Y. Fan, R. Kalaba, and I. J. E. Moore, “Arriving on time,” Journal of Optimization Theory and Applications, Vol. 127, No. 3, pp. 485-496, December 2005, Gao, S. and Chabini, I., “Optimal Routing Policy Problems in Stochastic Time-Dependent Networks,” Proceedings of the IEEE 5th International Conference on Intelligent, Transportation Systems, pp. 549-559, 2002, and Boyan, J. and Mitzenmacher, M., “Improved Results for Route Planning in Stochastic Transportation Networks,” ACM-SIAM Symposium on Discrete Algorithms, 2001.
Few methods consider minimizing a nonlinear or nonmonotonic function of the length and only give approximate heuristic processes.
Mirchandani and Soroush give exponential processes and heuristics for quadratic utility functions, P. Mirchandani and H. Soroush, “Optimal paths in probabilistic networks: a case with temporary preferences,” Determiners and Operations Research, 12(4):365-381, 1985.